Several computer applications--digital signal processing in particular--require the repeated evaluation of a few specific functions. Usually, function values are obtained by computing the terms of a series to the required degree of precision. But this may be unacceptably slow, especially when there are real-time constraints. Alternative solutions are either table-lookups or special-purpose arithmetic units. But the table-lookup approach is useful only for limited-precision applications, since the table size grows exponentially with the argument precision, and special-purpose hardware designed for each required function may be expensive and inflexible.
A number of previous works have reported on the design of special-purpose hardware for the evaluation of particular functions. The base-two logarithm and exponential have been the functions most considered, because of the usefulness of the logarithmic transformation in multiplication, division, and exponentiation.
The work of Mitchell is a fundamental exposition of the idea of implementing the log function in hardware. Any positive number y can be written in the form y=2.sup.k x, where k is an integer and x is between one and two. Mitchell proposes using the straight line x-1 as an approximation to log.sub.2 x for 1.ltoreq.x.ltoreq.2. But the straight-line approximation has a maximum absolute error of 0.086 in the interval. This can lead to an error of 11.1 percent for multiplication implemented by logarithms.
Combet et al. propose using several straight-line segments for the approximation of log.sub.2 x. The coefficients of the linear segments are selected for efficient implementation in hardware as well as reduction of the maximum error. The study results in a hardware design that uses four segments, reducing the maximum error to 0.008.
Hall, Lynch, and Dwyer also propose the piecewise linear approximation to the logarithm, as well as to the exponential. Their analysis is based on the minimization of the squared error. Numerical results are shown for approximations by up to eight segments. The maximum error of the least-squares linear approximation to log.sub.2 x is shown to be 0.065 for one segment, and 0.0062 for four segments (compare to the cases above). For eight segments, the error is 0.00167 - approximately a fourfold reduction over the four-segment case. The use of the log-exp transformation is shown for a digital filter, requiring 6-bit precision.
A work by Marino considers the use of two second-degree polynomial segments to approximate log.sub.2 x. The computation of x.sup.2 is approximated in order to reduce it to adding and shifting operations. A maximum absolute error of 0.0040 is achieved for log.sub.2 x.
Brubaker and Becker analyze the evaluation of logarithms and exponentials by ROM table-lookup without interpolation. They consider multiplication by direct table-lookup and by the addition of logarithms. Their highest precision example is a multiplication with an error of 0.1 percent, in which the operands are 11 bits and the product 10 bits. In this case, the memory required for multiplication via logarithms is smaller by a factor of 50 than that required for direct table-lookup.
Several studies have shown the effectiveness of the logarithm form of number representation, both for fast and significant computation, and for efficient use of storage. But the practical usefulness of logarithmic representation schemes depends critically on efficient conversions through the logarithm and exponential functions.
A recent work by Lo and Aoki shows how these functions can be evaluated quickly through the use of a programmable logic array (PLA). Their scheme is to use the single-segment linear approximation for log.sub.2 x for 1.ltoreq.x.ltoreq.2, but then to add error-correcting values obtained from a PLA. The error corrections, truncated to the precision required of the result, are found to be constant in intervals of x. Economy in the required PLA size is obtained by encoding it to provide corrections for each group of x values. The speed of this technique is significant: the result is obtained after only two logic levels in the PLA, followed by one addition.
The same authors have also demonstrated iterative techniques for the evaluation of the logarithm. These methods are implemented with a smaller hardware investment, but are correspondingly slower.